package SubjectBacktracking.Three;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsWithDup {

/**
 * 难度：中等
 * 
 * 90. 子集 II
 * 	给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * 	说明：解集不能包含重复的子集。
 * 	示例:
 * 	输入: [1,2,2]
 * 	输出:
 * 	[
 * 	  [2],
 * 	  [1],
 * 	  [1,2,2],
 * 	  [2,2],
 * 	  [1,2],
 * 	  []
 * 	]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SubsetsWithDup swd = new SubsetsWithDup();
		System.out.println(swd.subsetsWithDup(new int[] {1,2,2}));
	}

	List<List<Integer>> result = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		boolean[] used = new boolean[nums.length];
		Arrays.sort(nums);
		backtracking(nums, 0, used);
		return result;
    }
	private void backtracking(int[] nums, int startIndex,boolean[] used) {
		result.add(new ArrayList<>(path));
		
		for(int i=startIndex;i<nums.length;i++) {
			if(i>0 && nums[i] == nums[i-1] && used[i-1] == false) {
				continue;
			}
			path.add(nums[i]);
			used[i] = true;
			backtracking(nums, i+1, used);
			used[i] = false;
			path.remove(path.size()-1);
		}
	}
}
